home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 7981 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.3 KB
  1. Path: walters.East.Sun.COM!usenet
  2. From: Henry Wong <henry.wong@sun.com>
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: Fri, 16 Feb 1996 14:43:01 -0500
  6. Organization: Sun Microsystems, Inc.
  7. Message-ID: <3124DE45.CEB@sun.com>
  8. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com> <4fv74c$chq@gatekeeper.alcatel.no>
  9. NNTP-Posting-Host: enchanter.east.sun.com
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 2.0b6a (X11; I; SunOS 5.4 sun4m)
  14. CC: sven.pran@alcatel.no, clelaj@born.com, thecrow@iconn.net
  15.  
  16. > >The Crow wrote:
  17. > >>
  18. > >> Here is what I am trying to do, I want to find the last NON-ZERO
  19. > >> digit of a given factorial.  For instance,
  20. > >>
  21. > >> 5! = 120
  22. > >>
  23. > >> so the last non-zero digit is 2.  I want to be able to do this 
  24. > >> up to 1000. Problem is, no matter how huge of a data-type you use,
  25. > >> there isn't any way for the computer to handle 1000!, it is
  26. > >> however possible to find the last non-zero digit somehow.  One
  27. > >> thing I have tried is as I went through multiplying the series of
  28. > >> numbers in the factorial (5 * 4 * 3 * 2) I would remove all the
  29. > >> trailing ZEROS, I got this to work up to 789, but it wont
  30. > >> work with 1000 and i am not really sure why.  If anyone has a
  31. > >> clue how I can do this let me know.
  32. > >
  33.  
  34. Believe it or not, you do not need a brute force calculation to find
  35. the answer. Simply look at it another way...
  36.  
  37. How do you add a zero to a number? answer, multiply it by 10, which
  38. means that broken down to primes, multiple it by 2 and 5.
  39.  
  40. Well, you get a two everytime you multiply an even number, and you
  41. get a five every time it is divisiable by 5. Since, there is more even
  42. numbers than every 5, then you can say "the number of zeros at the
  43. end is the number of fives, when the number is broken down to primes"
  44.  
  45. Obvious, you get a 5 at every 5, so there are (1000/5) = 200 obvious
  46. fives. You also get a extra 5 at every 25 so there are (1000/25) = 40
  47. fives from that. Well, you get the pattern...
  48.  
  49.     (1000/5) = 200
  50.     (1000/25) = 40
  51.     (1000/125) = 8
  52.     (1000/625) = 1
  53.     ---------------
  54.             249 fives or 249 trailing zeros
  55.  
  56. This will of course break when it hits 3125! which can be solved
  57. by adding another term.
  58.